package cn.lishiyuan.leetcode;


/**
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 2
 * 输出：2
 * 解释：有两种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶
 * 2. 2 阶
 * 示例 2：
 *
 * 输入：n = 3
 * 输出：3
 * 解释：有三种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶 + 1 阶
 * 2. 1 阶 + 2 阶
 * 3. 2 阶 + 1 阶
 *
 */
public class LeetCode70 {

    /**
     * 递归解法
     * @return
     */
    public int recursion(int n){
        if(n<1){
            return 0;
        }
        // 只有一个台阶的时候只有一种解法
        if(n==1) return 1;

        // 只有两个台阶的有两种解法（走一次两个台阶、走两次一个台阶）
        if(n==2) return 2;

        // 走n个台阶有两种走法，走一步和走两步。所以n阶的走法就是走n-1台阶和走n-2台阶的和。
        return recursion(n-1)+recursion(n-2);
    }

    /**
     * 改循环
     * @return
     */
    public int recursionToFor(int n){
        if(n<1){
            return 0;
        }
        // 只有一个台阶的时候只有一种解法
        if(n==1) return 1;

        // 只有两个台阶的有两种解法（走一次两个台阶、走两次一个台阶）
        if(n==2) return 2;

        // n-1台阶的走法
        int oneStep=2;

        // n-2台阶的走法
        int twoStep=1;

        int nowStep=0;
        for(int i=3;i<=n;i++){
            nowStep = oneStep + twoStep;
            twoStep = oneStep;
            oneStep = nowStep;
        }
        // 走法
        return nowStep;
    }

    /**
     * 递归解法优化，添加缓存，优化分支
     * @return
     */
    public int recursionPro(int n,int[] cache){

        if(n<1){
            return 0;
        }

        // 只有一个台阶的时候只有一种解法
        if(n==1) return 1;

        // 只有两个台阶的有两种解法（走一次两个台阶、走两次一个台阶）
        if(n==2) return 2;

        if(cache[n-1] > 0) return cache[n-1];

        cache[n-1] = recursionPro(n-1,cache)+recursionPro(n-2,cache);

        return cache[n-1];
    }

}
